情報理学I 第3回レポート
tex-button.icon
/icons/hr.icon
情報理学第3回レポート
問1
https://gyazo.com/47a3f3010b43397628a7ce967bd63fca
問2
ナップサック問題は、以下のような問題と言える。
$ n個の品物があり、i 番目の品物のそれぞれ重さと価値が $ w(i), v(i) となっている ($ i=0,1,...,n−1)。
これらの品物から重さの総和が $ W を超えないように選んだときの、価値の総和の最大値を求めよ。
やさしいナップサック問題は、これに以下の条件を追加したものである。
品物の重さと価値は比例する $ v(i)/w(i) = a ただし $ a は実数。
いずれの品物についても、その品物の重さはより軽い品物すべての重さの総和より大きい。
また、$ w(i), v(i)は昇順にソートされているとする。
この条件の下での解法を以下に示す。
まず、キャパシティ$ Wを越えないような重さの1つのアイテムを探索する。それが$ j番目だとすると、
$ w(j) = Wの場合：答えは$ v(i)
$ w(j) < Wの場合：答えは $ \Sigma_{k = 0}^jv(k)
となる。
/icons/hr.icon